package codingStudy.moocAlgorithm;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Scanner;

/**
 * Recursion——递归相关练习
 * 
 * @author dell
 * @category
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
  */
public class Recursion {

	/**
	 * 17.letter combinations of a Phone Number
	 * 
	 * @param digits
	 * @return 数字字符串能表示的所有字母组合
	 */
	final private static String[] letterMap = { " ", "", "abc", "def", "ghi",
			"jkl", "mno", "pqrs", "tuv", "wxyz" };
	private static String digitsLetter;
	private static List<String> res;

	static List<String> letterCombinations(String digits) {

		digitsLetter = new String(digits);
		res = new ArrayList<String>();
		solve(0, "");
		return res;

	}

	private static void solve(int index, String str) {

		if (index == digitsLetter.length()) {
			res.add(str);
			return;
		}
		int numbers = digitsLetter.charAt(index) - '0';
		String letter = letterMap[numbers];
		for (int i = 0; i < letter.length(); i++) {
			String str1;
			str1 = str + letter.charAt(i);
			solve(index + 1, str1);
		}
		return;

	}

	/**
	 * 递归练习-93.Restore IP Addresses
	 * 
	 * @param s
	 * @return
	 */
	public static List<String> restoreIpAddresses(String s) {

		res = new ArrayList<String>();
		solveIP(s, "", 0, 1);
		return res;

	}

	private static void solveIP(String ipString, String IP, int index, int num) {
		// TODO Auto-generated method stub
		if (num > 4) {
			if (index == ipString.length())
				res.add(IP);
			return;
		}

		for (int i = 1; i < 4; i++) {
			int end = index + i;
			if (end > ipString.length()) {
				return;
			}
			String subString = ipString.substring(index, end);

			int number = Integer.parseInt(subString);
			if (number > 255)
				return;
			else {
				String stringIp;
				if (num == 4)
					stringIp = IP + subString;
				else
					stringIp = IP + subString + ".";

				solveIP(ipString, stringIp, end, num + 1);
			}

		}
	}

	/**
	 * 递归-排列问题 49. Permutations
	 * 
	 */

	private static List<List<Integer>> perRes;

	private static int lengthArray = 0;

	private static boolean[] flags;

	static List<List<Integer>> permute(int[] nums) {
		lengthArray = nums.length;
		perRes = new ArrayList<List<Integer>>();
		List<Integer> listRes = new ArrayList<Integer>();
		flags = new boolean[lengthArray];
		for (int i = 0; i < lengthArray; i++) {
			flags[i] = false;// false:表示没有访问过
		}
		solvePermute(nums, listRes, 1);
		return perRes;

	}

	static void solvePermute(int[] array, List<Integer> temRes, int index) {
		if (index > lengthArray) {
			perRes.add(new ArrayList<Integer>(temRes));
			return;
		}
		for (int i = 0; i < array.length; i++) {
			if (!flags[i]) {
				Integer a = array[i];
				temRes.add(a);
				flags[i] = true;
				solvePermute(array, temRes, index + 1);
				temRes.remove(a);
				flags[i] = false;
			}
		}

	}

	/**
	 * 递归-组合问题77. Combinations
	 */
	private static int kNums;

	static List<List<Integer>> combine(int n, int k) {

		if (k > n || n == 0 || k < 0)
			return null;
		kNums = k;
		List<Integer> listRes = new ArrayList<Integer>();
		perRes = new ArrayList<List<Integer>>();

		solveCombine(n, 1, listRes);
		return perRes;

	}

	static void solveCombine(int n, int start, List<Integer> temRes) {
		if (temRes.size() == kNums) {
			perRes.add(new ArrayList<Integer>(temRes));
			return;
		}
		for (int i = start; i < n + 1; i++) {
			Integer a = i;
			temRes.add(a);
			solveCombine(n, i + 1, temRes);
			temRes.remove(a);
		}

	}

	public static void main(String[] args) {
		// List<String> res = letterCombinations("23");
		// List<String> res = restoreIpAddresses("25525511135");
		// int[] nums = { 1, 2, 3, 4 };

		List<List<Integer>> res = combine(15, 5);
		System.out.println(res.size());
/*		
		for (List<Integer> list : res) {
			System.out.println(list);
		}
*/
	}

}
